package 链表.单向.练习;
//给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Text_5 {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode as = null;
        ListNode ae = null;

        ListNode bs = null;
        ListNode be = null;

        ListNode cur = pHead;
        while(cur!= null){
            if(cur.val<x){
                if(as==null){
                    as= ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }else{
                if(bs==null){
                    bs = be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }
            cur = cur.next;
        }
        //合并
        //可能出现前段为null,后段不为null
        if(as ==null){
            return bs;
        }
        ae.next = bs;
        if(bs!=null){
            be.next = null;//避免出现死循环
        }
        return as;
    }
}